package newcoder_exp.justPractise;
import java.util.*;
import org.junit.Test;

public class Pra2 {
    
    public int minTimes(int[] nums) {//[0...n]
        return dfs(nums, 1, nums.length - 1); //(p0, p1)即C1，(p1, p2)即C2, ..., (pn-1,pn)为Cn
        //第i个矩阵的起始点为p(i-1),终点为pi
    }

    //nums[0...n]矩阵可以确定一个矩阵链(C1, C2, ..., Cn)
    // 而每个分割位置由位于(Ci, C(i+1))间，共n-1个
    public int dfs(int[] nums, int left, int right) {
        //划分：[(left, (left + 1...right)], [(left, left + 1), (LEFT + 2....)],
        //[(left,....right-1), right] 一个下标表示一个矩阵
        if (left == right) {
            return 0;
        }
        //两个矩阵相邻，还是需要计算(p(i-1)*pi*p(i+1)次)
        // if (left + 1 == right) {
        //     return 1;
        // }

        int min = Integer.MAX_VALUE, t;
        for (int i = left; i < right; i++) {
            //左边：left...i, 这个矩阵的维度为(nums[left-1],nums[i])[最左矩阵左维度和最右矩阵右维度]
            t = dfs(nums, left, i) + dfs(nums, i + 1, right) + 
            nums[left - 1] * nums[i] * nums[right]; //最后一轮计算：(left-1, i) (i, right)
            min = Math.min(t, min);
        }
        return /* min == Integer.MAX_VALUE ? 1 : */ min;
    }



    public int minTimes2(int[] nums) {//[0...n]
        int n = nums.length - 1;
        //f[i][j]表示Ci矩阵到Cj矩阵的矩阵链的最小乘法次数
        //矩阵总数n个, 从1开始计数, 丢弃i,j为0的情况,方便取出维度
        int[][] f = new int[n + 1][n + 1];
        //f[i][j](i == j), 默认为0
        //按照列的方向填表，从下至上，从左往右

        //使用s[i][j]矩阵记录每个子区间应该划分的地方
        int[][] s = new int[n + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            for (int i = j - 1; i > 0; i--) {
                //遍历插入点的位置, [i, k], [k + 1, j]
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    // f[i][j] = Math.min(f[i][k] + f[k + 1][j] 
                    // + nums[i - 1] * nums[k] * nums[j], f[i][j]); 
                    int t = f[i][k] + f[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
                    if (f[i][j] > t) {
                        s[i][j] = k;
                        f[i][j] = t;
                    }
                }
            }

        }
        System.out.println(Arrays.deepToString(f));

        // 通过s[i][j]得到每个划分位置
        devide(s, 1, n);
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

        return f[1][n];
    }
    Queue<Integer> queue = new PriorityQueue<>();
    int idx = 1;
    public void devide(int[][] s, int lo, int hi) {
        if (lo == hi) {
            // queue.offer(lo);
            return;
        }
        // if (lo == hi - 1) {
        //     queue.offer(s[lo][hi]);
        //     return;
        // }
        int mid = s[lo][hi];
        // System.out.println("按照第" + mid + "个矩阵划分, 计算c" + lo + "*c" + mid
        // + "以及c" + (mid + 1) + "*c" + hi);
        devide(s, lo, mid);
        devide(s, mid + 1, hi);
        String ans = "";
        if (lo != mid) {
            ans += "第"+idx+"步，按照第" + mid + "个矩阵划分, 计算c" + lo + "*c" + mid;
            idx++;
        } else {
            ans += "第"+idx+"步，按照第" + mid + "个矩阵划分, 左半部分为c" + lo + ", 可以直接得到";
            idx++;
        }
        if (mid + 1 != hi) {
            ans += ", 计算c" + lo + "*c" + mid+ "以及c" + (mid + 1) + "*c" + hi;
        } else {
            ans += ", 右半部分为c" + hi + ", 可以直接得到";
        }

        System.out.println(ans);
    }

    @Test
    public void test() {
        // Solution s = new Solution();
        //10*100 , 100*5 , 5*50
        int[] nums = new int[]{30,35,15,5,10,20,25};
        int res = minTimes2(nums);
        System.out.println(res);
        // System.out.println(Integer.MIN_VALUE);
    }

}
